Autonomous vehicle (AV) navigation in some cases uses a high resolution three-dimensional (3D) model of the surroundings of the vehicle. The 3D model is formed by defining a 3D grid of spaces and tracking points entering and exiting the spaces to understand what space is free, filled, or unknown due to sensor occlusion. In some cases, the system identifies groups of points belonging to an object without regard to the identity of the object. The grouping can be used to simplify the tracking of points as well as to infer the state of unknown spaces in the grid that are occluded by other objects in the surroundings.
For example, when a group of points moves behind an object the system may reasonably conclude that the space behind the occlusion is occupied by that object and not free space. As the group of points exits the occluded area, the system may reasonably conclude that the occluded space is now free or at least that it is vacated by the object.
Lidar, for example, can be used to generate a 3D point cloud and to track the movement of points in that cloud. The movement can be tracked in all three dimensions so that lidar data is particularly well suited to generating a high resolution 3D model of the surroundings.
In some cases, the points in the point cloud are grouped together on the basis of comparing motion vectors of all of the points over time. A set of points with common, or consistent motion vectors, i.e. a clump of points traveling with the same velocity and acceleration are identified as belonging to a common object and are then grouped together and treated as a single object. Grouping the points reduces the compute load by modeling a group of multiple points in the surroundings as a single object instead of as multiple independent points.